#include <iostream>
using namespace std;
#include <IteratorRegister.h>
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
inline U64 FastXToTheN( const U64 x, const U64 n ) {
   if( x == 2 ) { return 1ULL << n;           }
   if( x == 4 ) { return 1ULL << n << n;      }
   if( x == 8 ) { return 1ULL << n << n << n; }
   assert( false );
   return 0ULL;
}
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
inline bool NodeIsSparse( const BNode & n ) {
   if( n.s[0] == 0 || n.s[1] == 0 ) { return true; }
   return false;
}
inline bool NodeIsSparse( const QNode & n ) {
   U32 nnz = 0;
   for( U32 i = 0; i < 4; i++ ) {
      if( n.s[i] != 0 ) { nnz++; }
   }
   
   // -- TODO -- test/regress
   // -- previous code -- assert( nnz );
   // -- previous code -- if( nnz == 1 ) { return true; }
   // --
   // -- current code:
   if( nnz <= 1 ) { return true; }
   return false;
}
inline bool NodeIsSparse( const ONode & n ) {
   U32 nnz = 0;
   for( U32 i = 0; i < 8; i++ ) {
      if( n.s[i] != 0 ) { nnz++; }
   }
   if( nnz == 1 ) { return true; }
   return false;
}
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
template < typename node_t, typename T > IteratorRegister< node_t, T >::IteratorRegister( const U32 _deg, const bool pcEnable, DedupMem< node_t > & _ddm ) :
   nopc( !pcEnable ),
   deg( _deg ),
   ptrsSize( sizeof( U32 ) ),
   leafSize( sizeof(  T  ) ),
   nodeSize( 4*_deg ),
   numLeafPerNode( nodeSize / leafSize ),
   numPtrsPerLeaf( leafSize / ptrsSize ),
   leafPosMask( numLeafPerNode - 1 ),
   nsa( Log2Ceil( numLeafPerNode ) ),
   psa( Log2Ceil( _deg ) ),
   pmin( 0x80000000 ),
   ddm( _ddm )
{
   hgt = 0;
   lvl = 0;
   nnz = 0;
   sp  = 0;
   pathLowerBound = 0ULL;
   pathUpperBound = 0ULL;
   currLeafPos = 0ULL;
   currNodePos = 0ULL;
   ZeroNode( zeroNode );
   
   ZeroNode( newNodes [ sp ] );
   ZeroNode( oldNodes [ sp ] );
   vpath    [ sp ] = 0;
   sp++;
}
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
template < typename node_t, typename T > void IteratorRegister< node_t, T >::SetLeafVal( const double v ) {
   LSU u;
   u.d = v;
   
   const U32 path = currLeafPos & leafPosMask;
   
   sp--;
   const U32 nodeOff = numLeafPerNode - 1 - path;
   newNodes [ sp ].l[ nodeOff ] = u.l;
   sp++;
   nnz++;
   unzMap[ v ] += 1;
}
template < typename node_t, typename T > void IteratorRegister< node_t, T >::SetLeafVal( const S32 v ) {
   
   const U32 path = currLeafPos & leafPosMask;
   
   sp--;
   const U32 nodeOff = numLeafPerNode - 1 - path;
   newNodes [ sp ].s[ nodeOff ] = v;
   sp++;
   nnz++;
   unzMap[ v ] += 1;
}
template < typename node_t, typename T > void IteratorRegister< node_t, T >::Audit( void ) const {
   ddm.Audit();
}
template < typename node_t, typename T > void IteratorRegister< node_t, T >::PopLevel( void ) {

   if( lvl == hgt ) {
      // handle expansion
      hgt++;
      lvl++;

      pathLowerBound = 0ULL;
      pathUpperBound = FastXToTheN( deg, hgt );
      
      for( U32 spp = hgt; spp > 0; spp-- ) {
         newNodes [ spp ] = newNodes [ spp-1 ];
         oldNodes [ spp ] = oldNodes [ spp-1 ];
         vpath    [ spp ] = vpath    [ spp-1 ];
      }
      
      // faster than assigning, i.e. faster than "nodeNodes[0] = zeroNode;"?
      ZeroNode( newNodes[0] );
      ZeroNode( oldNodes[0] );
      vpath[ 0 ] = 0;
   }
   else {
      sp--;
      const U32 path = vpath[ sp ];         
      const U64  inc = FastXToTheN( deg, lvl );
      pathLowerBound -= path * inc;
      pathUpperBound += ( (deg - 1) - path ) * inc;
      lvl++;
   }
}
template < typename node_t, typename T > void IteratorRegister< node_t, T >::PushLevel( const U64 nodePos ) {

   lvl--;
   
   U32 path = 0;
   U64 inc  = FastXToTheN( deg, lvl );
   pathUpperBound = pathLowerBound + inc;
   
   while( !PathContainsNodePos( nodePos ) ) {
      path += 1;
      pathLowerBound += inc;
      pathUpperBound += inc;
   }

   const U32 nodeOff = deg - 1 - path;
   U32 plid = newNodes[ sp - 1 ].s[ nodeOff ];
   if( plid != 0 ) {
      // -- cout << "pread()" << endl;
      node_t child = ddm.pread( plid );

      oldNodes [ sp ] = child;
      newNodes [ sp ] = child;
   }
   else {
      ZeroNode( oldNodes[ sp ] );
      ZeroNode( newNodes[ sp ] );
   }
   vpath[ sp ] = path;
   sp++;
}
template < typename node_t, typename T > void IteratorRegister< node_t, T >::CommitPath( void ) {
   
   U32 p = psa;     // path shift amount: psa == log2( degree )
   U32 path = 0;    // location for plid in parent node
   U32 plen = 0;    // length of path compaction
   U32 plid = 0;    // plid returned by lookup operation
   bool pc = false; // patch compaction in progress
   
   // 32 bits to store the path compaction
   // save room for 1) path stop bits 2) terminating path bits
   const U32 maxlen = 32 - psa - psa;

   for( U32 spp = hgt; spp > sp; spp-- ) {

      if( nopc || !NodeIsSparse( newNodes[spp] ) ) {

         plid = ddm.Lookup( newNodes [ spp ], hgt-spp );
         path = vpath[ spp ];
         const U32 nodeOff = deg - 1 - path;
         newNodes[ spp-1 ].s[ nodeOff ] = plid;
         continue;
      }
      if( spp < hgt ) {
         
         if( newNodes[ spp-1 ] == zeroNode && plen < maxlen ) {
            // if the parent node is zero,
            // start, or continue, a path compaction
            if( !pc ) {
               // start pc
               pc = true;
               p <<= psa;
               p  |= path;
               plen += psa;
            }
            else {
               // continue pc
               p <<= psa;
               p  |= path;
               plen += psa;
            }
         }
         else {
            if( pc ) {
                              
               // terminate a pc
               // see (2) above in maxlen comments
               pc = false;
               p <<= psa;
               p  |= path;

               node_t node;
               ZeroNode( node );
               // assert( plid < pmin );
               node.s[ deg-1 ] = pmin | plid;
               node.s[ deg-2 ] = p;
               p = psa;
               plen = 0;
               plid = ddm.Lookup( node, hgt-spp );
            }
            else {
               //const node_t & oldNode = oldNodes [ spp ];
               plid = ddm.Lookup( newNodes [ spp ], hgt-spp );
               //ddm.DecRC( oldNode );
            }
         }
      }
      else {
         // leaf node
         assert( spp == hgt );
         plid = ddm.Lookup( newNodes [ spp ], hgt-spp );
      }
      
      path = vpath[ spp ];
      const U32 nodeOff = deg - 1 - path;
         
      newNodes[ spp-1 ].s[ nodeOff ] = plid;
   }
   
   if( pc ) {
      p <<= psa;
      p  |= path;
      
      node_t node;
      ZeroNode( node );
      assert( plid < pmin );
      node.s[ deg-1 ] = pmin | plid;
      node.s[ deg-2 ] = p;
      
      const U32 plid    = ddm.Lookup( node, hgt-sp );
      const U32 path    = vpath[ sp ];
      const U32 nodeOff = deg - 1 - path;
      newNodes[ sp-1 ].s[ nodeOff ] = plid;
   }
   else {
      const U32 plid    = ddm.Lookup( newNodes[ sp ], hgt-sp );
      const U32 path    = vpath[ sp ];
      const U32 nodeOff = deg - 1 - path;
      newNodes[ sp-1 ].s[ nodeOff ] = plid;
   }
}
template < typename node_t, typename T > void IteratorRegister< node_t, T >::Commit( DagMtx< node_t > & dagmtx ) {

   if( hgt == 0 ) {
      const U32 plid    = ddm.Lookup( newNodes[ 0 ], 0 );
      root = plid;
      return;
   }
   while( lvl!= hgt ) {
      PopLevel();
   }
   
   CommitPath();
   U32 plid = ddm.Lookup( newNodes[0], hgt );
   root = plid;
   
   const U32 dagIdx = dagmtx.numDags;

   DagStatistics ds;
   dagmtx.dagStats.push_back( ds );

   ddm.TransferStats( dagmtx.dagStats[ dagIdx ], Hgt() );

   dagmtx.dagStats[ dagIdx ].deg = deg;
   dagmtx.dagStats[ dagIdx ].leafSize = double( dagmtx.arrStats[ dagIdx ].numBytes ) / double( dagmtx.arrStats[ dagIdx ].numElems );
   dagmtx.dagStats[ dagIdx ].nnzLeafElems  = nnz;
   dagmtx.dagStats[ dagIdx ].leafUniqElems = unzMap.size();
   dagmtx.dagStats[ dagIdx ].totLeafElems  = dagmtx.arrStats[ dagIdx ].numElems;
   dagmtx.dagStats[ dagIdx ].leafVirtNodes = dagmtx.dagStats[ dagIdx ].virtNodes[ 0 ];
   dagmtx.dagStats[ dagIdx ].leafUniqNodes = dagmtx.dagStats[ dagIdx ].uniqNodes[ 0 ];
   dagmtx.dagStats[ dagIdx ].totalNumNodes = dagmtx.dagStats[ dagIdx ].TotalNodeCount();
   
   dagmtx.dagRootIdxs.push_back( root/dagmtx.deg );
   dagmtx.dagHgts.push_back( 1+Hgt() );
   dagmtx.numDags++;
}
template < typename node_t, typename T > void IteratorRegister< node_t, T >::SetLeafPos( const U64 reqdLeafPos ) {
   // check to see if we are already there
   if( currLeafPos == reqdLeafPos ) { return; }
   
   // check if node pos is already there
   const U64 reqdNodePos = reqdLeafPos >> nsa; // == reqdLeafPos / numLeafPerNode;
   if( currNodePos == reqdNodePos ) {
      
      currLeafPos = reqdLeafPos;
      return;
   }
   
   while( !PathContainsNodePos( reqdNodePos ) ) {
      PopLevel();
   }

   CommitPath();

   while( lvl > 0 ) {
      PushLevel( reqdNodePos );
   }
   currLeafPos = reqdLeafPos;
   currNodePos = reqdNodePos;
}
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
template class IteratorRegister< BNode, double >;
template class IteratorRegister< ONode, double >;
template class IteratorRegister< QNode, double >;
template class IteratorRegister< BNode, S32 >;
template class IteratorRegister< ONode, S32 >;
template class IteratorRegister< QNode, S32 >;
